package cn.tedu.decode;

import java.util.Scanner;

/**
 * 假设现在需要对一串数字字符串进行解码，我们知道该字符串的编码规则是
 * 1->A
 * 2->B
 * ...
 * 26->Z
 * 输出数字N 代表有多少种可能的结果
 * <p>
 * 输入描述:
 * 一个整数
 * <p>
 * 输出描述:
 * 一个整数
 * <p>
 * 输入例子1:
 * 111
 * <p>
 * 输出例子1:
 * 3
 * <p>
 * 例子说明1:
 * AAA AK KA 三种可能性
 */
public class NumberToCharacter {
    public static void main(String[] args) {
         Scanner input = new Scanner(System.in);
         String text = input.nextLine();
         int res = numDecodings(text);
         System.out.println(res);
    }

    /**
     * 非递归版，用一个一维数组存储每一个字符位置的计算结果
     * @param s
     * @return
     */
    private static int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            String sub = s.substring(i - 2, i);
            int num = Integer.parseInt(sub);
            if (10 <= num && num <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[s.length()];
    }

    /**
     * 递归版, 不存储中间结果，直接递归运算
     * @param s
     * @return
     */
    private static int recNumDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        if (s.length() == 1)
            return 1;
        if (s.length() == 2) {
            int num = Integer.parseInt(s);
            if (s.charAt(1) == '0')
                return 1;
            if (10 <= num && num <= 26)
                return 2;
            return 1;
        }

        int count = 0;
        if (s.charAt(s.length() - 1) != '0') {
            count += recNumDecodings(s.substring(0, s.length() - 1));
        }
        String sub = s.substring(s.length() - 2);
        int num = Integer.parseInt(sub);
        if (10 <= num && num <= 26) {
            count += recNumDecodings(s.substring(0, s.length() - 2));
        }
        return count;
    }
}
